package com.rd.teacher.jichao.day28;

public class Test {

    // 简单的思路是  先求出head链表的长度
    // 通过长度和k值  求出正数的位置
    // 1->2->3->4->5, 和 k = 2.
    // 如果长度为5  那么倒数第2个  是正数的第四个  5-2+1=4
    // 如果长度为n  那么倒数第k个  是正数的第 n-k+1个
    public static ListNode getKthFromEnd(ListNode head, int k) {
        int n = 0;
        ListNode tmp = head;
        while (tmp.next != null) {
            tmp = tmp.next;
            n++;
        }
        System.out.println(n);

        // 求正数的第n-k+1个节点
        // 1->2-> .. -> 5
        // n=4  k=2
        // n-k+1 = 3
        tmp = head;
        for (int i = 0; i < n - k + 1; i++) {
            tmp = tmp.next;
        }

        System.out.println(tmp);
        return tmp;
    }

    // 快慢指针
    // 快的指针从正数第k个节点开始
    // 慢的指针从头节点开始
    public static ListNode getKthFromEnd1(ListNode head, int k) {
        ListNode slow = head;
        ListNode fast = head;
        for (int i = 1; i < k; i++) {
            fast = fast.next;
        }

        // 同时向后移动  一直到快指针走到链表的最后一个节点
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }


    public static void main(String[] args) {
        // 先构造一个链表  1->2->3->4->5 .. n
//        ListNode node = new ListNode(1);
//        ListNode node1 = new ListNode(2);
//        ListNode node2 = new ListNode(3);
//        ListNode node3 = new ListNode(4);
//        node.next = node1;
//        node1.next = node2;
//        node2.next = node3;
//
//        System.out.println(node);

        // 如果要构造一个从1-n的链表
        ListNode head = new ListNode(1);
        int n = 5;
        // 1->2-> ... -> n
        ListNode pre = head;
        for (int i = 2; i <= n; i++) {
            // i=2  head.next = listNode
            // i=3
            ListNode listNode = new ListNode(i);
            pre.next = listNode;
            pre = listNode;
        }

        getKthFromEnd1(head, 2);
//        System.out.println(head);
    }


}

